package dongtai;

public class liusiqi {
    public static int countSubstrings(String s) {
        int n=s.length();
        if(n==1){
            return 1;
        }
        //默认为false的
        boolean[][] f=new boolean[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                char first=s.charAt(i);
                char last=s.charAt(j);
                if(first!=last){
                    f[i][j]=false;
                }else{
                    if(i==j){
                        f[i][j]=true;
                        continue;
                    }
                    if(i+1==j){
                        f[i][j]=true;
                        continue;
                    }
                    if(f[i+1][j-1]){
                        f[i][j]=true;
                    }
                }
            }
        }
        //遍历二维dp表
        //返回true的个数
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if(f[i][j]){
                    count++;
                }

            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s="abc";
        int m = countSubstrings(s);
        System.out.println(m);
    }
}
